<!DOCTYPE html><html lang="zh-CN" data-theme="light"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width,initial-scale=1"><title>LeetCode每日一道 | 小李博客</title><meta name="keywords" content="LeetCode"><meta name="author" content="小李博客"><meta name="copyright" content="小李博客"><meta name="format-detection" content="telephone=no"><meta name="theme-color" content="#ffffff"><meta name="description" content="参考最新的官方解答，精品阅读推荐 || 人人都能看得懂的Leetcode力扣刷题教程合集 || Leetcode力扣 1-300题视频讲解合集 || Leetcode力扣 301+题视频讲解合集   算法性能分析参考👉一个视频教会你算法的时间复杂度 || 一个视频教会你算法的空间复杂度  时间复杂度 时间复杂度  算法的执行效率，算法的执行时间与算法的输入值之间的关系 以下例子，设语句执行时间为">
<meta property="og:type" content="article">
<meta property="og:title" content="LeetCode每日一道">
<meta property="og:url" content="http://xiaoliblog.cn/page/leetcode01.html">
<meta property="og:site_name" content="小李博客">
<meta property="og:description" content="参考最新的官方解答，精品阅读推荐 || 人人都能看得懂的Leetcode力扣刷题教程合集 || Leetcode力扣 1-300题视频讲解合集 || Leetcode力扣 301+题视频讲解合集   算法性能分析参考👉一个视频教会你算法的时间复杂度 || 一个视频教会你算法的空间复杂度  时间复杂度 时间复杂度  算法的执行效率，算法的执行时间与算法的输入值之间的关系 以下例子，设语句执行时间为">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://cdn.jsdelivr.net/gh/xiaoliblog/image@efa02577d8e4f5d49ebb4bd77f5647822d901ed8/2021/01/24/d99d6d32543e0965b25ee42a87ab34a9.png">
<meta property="article:published_time" content="2020-11-24T12:16:51.310Z">
<meta property="article:modified_time" content="2021-03-08T13:58:19.704Z">
<meta property="article:author" content="小李博客">
<meta property="article:tag" content="LeetCode">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://cdn.jsdelivr.net/gh/xiaoliblog/image@efa02577d8e4f5d49ebb4bd77f5647822d901ed8/2021/01/24/d99d6d32543e0965b25ee42a87ab34a9.png"><link rel="shortcut icon" href="https://cdn.jsdelivr.net/gh/xiaoliblog/image@6b5e7ef72be1c8973d94e5a9c49accbf775ad820/2021/02/01/c485da031fe0e464d04eaba8a66c4a8f.png"><link rel="canonical" href="http://xiaoliblog.cn/page/leetcode01"><link rel="preconnect" href="//cdn.jsdelivr.net"/><link rel="preconnect" href="//busuanzi.ibruce.info"/><link rel="stylesheet" href="/css/index.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free/css/all.min.css" media="print" onload="this.media='all'"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/node-snackbar/dist/snackbar.min.css" media="print" onload="this.media='all'"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/instantsearch.js@2.10.5/dist/instantsearch.min.css" media="print" onload="this.media='all'"><script src="https://cdn.jsdelivr.net/npm/instantsearch.js@2.10.5/dist/instantsearch.min.js" defer></script><script>const GLOBAL_CONFIG = { 
  root: '/',
  algolia: {"appId":"RTG4CPNBLJ","apiKey":"f1745bdad68ceec57653b78244fe332c","indexName":"MyBlogIndex","hits":{"per_page":6},"languages":{"input_placeholder":"搜索文章","hits_empty":"找不到您查询的内容：${query}","hits_stats":"找到 ${hits} 条结果，用时 ${time} 毫秒"}},
  localSearch: undefined,
  translate: {"defaultEncoding":2,"translateDelay":0,"msgToTraditionalChinese":"繁","msgToSimplifiedChinese":"簡"},
  noticeOutdate: undefined,
  highlight: {"plugin":"highlighjs","highlightCopy":true,"highlightLang":true,"highlightHeightLimit":200},
  copy: {
    success: '复制成功',
    error: '复制错误',
    noSupport: '浏览器不支持'
  },
  relativeDate: {
    homepage: false,
    post: false
  },
  runtime: '天',
  date_suffix: {
    just: '刚刚',
    min: '分钟前',
    hour: '小时前',
    day: '天前',
    month: '个月前'
  },
  copyright: {"limitCount":100,"languages":{"author":"作者: 小李博客","link":"链接: ","source":"来源: 小李博客","info":"著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"}},
  lightbox: 'mediumZoom',
  Snackbar: {"chs_to_cht":"你已切换为繁体","cht_to_chs":"你已切换为简体","day_to_night":"你已切换为深色模式","night_to_day":"你已切换为浅色模式","bgLight":"#49b1f5","bgDark":"#121212","position":"top-center"},
  source: {
    jQuery: 'https://cdn.jsdelivr.net/npm/jquery@latest/dist/jquery.min.js',
    justifiedGallery: {
      js: 'https://cdn.jsdelivr.net/npm/justifiedGallery/dist/js/jquery.justifiedGallery.min.js',
      css: 'https://cdn.jsdelivr.net/npm/justifiedGallery/dist/css/justifiedGallery.min.css'
    },
    fancybox: {
      js: 'https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@latest/dist/jquery.fancybox.min.js',
      css: 'https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@latest/dist/jquery.fancybox.min.css'
    }
  },
  isPhotoFigcaption: false,
  islazyload: false,
  isanchor: true
}</script><script id="config-diff">var GLOBAL_CONFIG_SITE = { 
  isPost: true,
  isHome: false,
  isHighlightShrink: false,
  isToc: true,
  postUpdate: '2021-03-08 21:58:19'
}</script><noscript><style type="text/css">
  #nav {
    opacity: 1
  }
  .justified-gallery img {
    opacity: 1
  }

  #recent-posts time,
  #post-meta time {
    display: inline !important
  }
</style></noscript><script>(win=>{
    win.saveToLocal = {
      set: function setWithExpiry(key, value, ttl) {
        if (ttl === 0) return
        const now = new Date()
        const expiryDay = ttl * 86400000
        const item = {
          value: value,
          expiry: now.getTime() + expiryDay,
        }
        localStorage.setItem(key, JSON.stringify(item))
      },

      get: function getWithExpiry(key) {
        const itemStr = localStorage.getItem(key)

        if (!itemStr) {
          return undefined
        }
        const item = JSON.parse(itemStr)
        const now = new Date()

        if (now.getTime() > item.expiry) {
          localStorage.removeItem(key)
          return undefined
        }
        return item.value
      }
    }
  
    win.getScript = url => new Promise((resolve, reject) => {
      const script = document.createElement('script')
      script.src = url
      script.async = true
      script.onerror = reject
      script.onload = script.onreadystatechange = function() {
        const loadState = this.readyState
        if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
        script.onload = script.onreadystatechange = null
        resolve()
      }
      document.head.appendChild(script)
    })
  
      win.activateDarkMode = function () {
        document.documentElement.setAttribute('data-theme', 'dark')
        if (document.querySelector('meta[name="theme-color"]') !== null) {
          document.querySelector('meta[name="theme-color"]').setAttribute('content', '#0d0d0d')
        }
      }
      win.activateLightMode = function () {
        document.documentElement.setAttribute('data-theme', 'light')
        if (document.querySelector('meta[name="theme-color"]') !== null) {
          document.querySelector('meta[name="theme-color"]').setAttribute('content', '#ffffff')
        }
      }
      const t = saveToLocal.get('theme')
    
          if (t === 'dark') activateDarkMode()
          else if (t === 'light') activateLightMode()
        
      const asideStatus = saveToLocal.get('aside-status')
      if (asideStatus !== undefined) {
        if (asideStatus === 'hide') {
          document.documentElement.classList.add('hide-aside')
        } else {
          document.documentElement.classList.remove('hide-aside')
        }
      }
    
    const fontSizeVal = saveToLocal.get('global-font-size')
    if (fontSizeVal !== undefined) {
      document.documentElement.style.setProperty('--global-font-size', fontSizeVal + 'px')
    }
    })(window)</script><link rel="stylesheet" href="/css/MyStyle/MyStyle.css" media="defer" onload="this.media='all'"/><link rel="stylesheet" href="/css/MyStyle/tagStyle.css" media="defer" onload="this.media='all'"/><link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/zykjofficial/zykjresource@master/css/font-awesome-animation.min.css" media="defer" onload="this.media='all'"/><link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/sviptzk/StaticFile_HEXO@latest/butterfly/css/font-awesome-animation.min.css" media="defer" onload="this.media='all'"><link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/sviptzk/StaticFile_HEXO@latest/butterfly/css/plugins.min.css" media="defer" onload="this.media='all'"><meta name="generator" content="Hexo 5.2.0"><link rel="alternate" href="/atom.xml" title="小李博客" type="application/atom+xml">
</head><body><div id="web_bg"></div><div id="sidebar"><div id="menu-mask"></div><div id="sidebar-menus"><div class="author-avatar"><img class="avatar-img" src="https://cdn.jsdelivr.net/gh/xiaoliblog/image@6b5e7ef72be1c8973d94e5a9c49accbf775ad820/2021/02/01/c485da031fe0e464d04eaba8a66c4a8f.png" onerror="onerror=null;src='/img/friend_404.gif'" alt="avatar"/></div><div class="site-data"><div class="data-item is-center"><div class="data-item-link"><a href="/archives/"><div class="headline">文章</div><div class="length-num">210</div></a></div></div><div class="data-item is-center"><div class="data-item-link"><a href="/tags/"><div class="headline">标签</div><div class="length-num">38</div></a></div></div><div class="data-item is-center"><div class="data-item-link"><a href="/categories/"><div class="headline">分类</div><div class="length-num">56</div></a></div></div></div><hr/><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 主页</span></a></div><div class="menus_item"><a class="site-page" href="/link/"><i class="fa-fw fas fa-link"></i><span> 友链</span></a></div><div class="menus_item"><a class="site-page" href="/box/"><i class="fa-fw fa fa-briefcase"></i><span> 工具箱</span></a></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><i class="fa-fw fas fa-book"></i><span> 找文章</span><i class="fas fa-chevron-down expand"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> 归档</span></a></li><li><a class="site-page child" href="/tags/"><i class="fa-fw fas fa-tags"></i><span> 标签</span></a></li><li><a class="site-page child" href="/categories/"><i class="fa-fw fa fa-folder-open"></i><span> 分类</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="/about/"><i class="fa-fw fa fa-address-card"></i><span> 关于</span></a></div><div class="menus_item"><a class="site-page" href="/messageboard/"><i class="fa-fw fa fa-paper-plane"></i><span> 留言</span></a></div></div></div></div><div class="post" id="body-wrap"><header class="not-top-img" id="page-header"><nav id="nav"><span id="blog_name"><a id="site-name" href="/">小李博客</a></span><div id="menus"><div id="search-button"><a class="site-page social-icon search"><i class="fas fa-search fa-fw"></i><span> 搜索</span></a></div><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 主页</span></a></div><div class="menus_item"><a class="site-page" href="/link/"><i class="fa-fw fas fa-link"></i><span> 友链</span></a></div><div class="menus_item"><a class="site-page" href="/box/"><i class="fa-fw fa fa-briefcase"></i><span> 工具箱</span></a></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><i class="fa-fw fas fa-book"></i><span> 找文章</span><i class="fas fa-chevron-down expand"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> 归档</span></a></li><li><a class="site-page child" href="/tags/"><i class="fa-fw fas fa-tags"></i><span> 标签</span></a></li><li><a class="site-page child" href="/categories/"><i class="fa-fw fa fa-folder-open"></i><span> 分类</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="/about/"><i class="fa-fw fa fa-address-card"></i><span> 关于</span></a></div><div class="menus_item"><a class="site-page" href="/messageboard/"><i class="fa-fw fa fa-paper-plane"></i><span> 留言</span></a></div></div><div id="toggle-menu"><a class="site-page"><i class="fas fa-bars fa-fw"></i></a></div></div></nav></header><main class="layout" id="content-inner"><div id="post"><div id="post-info"><h1 class="post-title">LeetCode每日一道</h1><div id="post-meta"><div class="meta-firstline"><span class="post-meta-date"><i class="far fa-calendar-alt fa-fw post-meta-icon"></i><span class="post-meta-label">发表于</span><time class="post-meta-date-created" datetime="2020-11-24T12:16:51.310Z" title="发表于 2020-11-24 20:16:51">2020-11-24</time><span class="post-meta-separator">|</span><i class="fas fa-history fa-fw post-meta-icon"></i><span class="post-meta-label">更新于</span><time class="post-meta-date-updated" datetime="2021-03-08T13:58:19.704Z" title="更新于 2021-03-08 21:58:19">2021-03-08</time></span><span class="post-meta-categories"><span class="post-meta-separator">|</span><i class="fas fa-inbox fa-fw post-meta-icon"></i><a class="post-meta-categories" href="/categories/%E7%AE%97%E6%B3%95/">算法</a></span></div><div class="meta-secondline"><span class="post-meta-separator">|</span><span class="post-meta-wordcount"><i class="far fa-file-word fa-fw post-meta-icon"></i><span class="post-meta-label">字数总计:</span><span class="word-count">3.5k</span><span class="post-meta-separator">|</span><i class="far fa-clock fa-fw post-meta-icon"></i><span class="post-meta-label">阅读时长:</span><span>14分钟</span></span><span class="post-meta-separator">|</span><span class="post-meta-pv-cv" id="" data-flag-title="LeetCode每日一道"><i class="far fa-eye fa-fw post-meta-icon"></i><span class="post-meta-label">阅读量:</span><span id="busuanzi_value_page_pv"></span></span></div></div></div><article class="post-content" id="article-container"><h1 id="参考"><a href="#参考" class="headerlink" title="参考"></a>参考</h1><div class="note success simple"><p><a target="_blank" rel="noopener" href="https://leetcode-cn.com/articles/?category=&search=1">最新的官方解答，精品阅读推荐</a> || <a target="_blank" rel="noopener" href="https://www.bilibili.com/video/BV1wA411b7qZ">人人都能看得懂的Leetcode力扣刷题教程合集</a> || <a target="_blank" rel="noopener" href="https://www.bilibili.com/video/BV1xa411A76q">Leetcode力扣 1-300题视频讲解合集</a> || <a target="_blank" rel="noopener" href="https://www.bilibili.com/video/BV1eK4y1j7fT">Leetcode力扣 301+题视频讲解合集</a></p>
</div>

<h1 id="算法性能分析"><a href="#算法性能分析" class="headerlink" title="算法性能分析"></a>算法性能分析</h1><div class="note success simple"><p>参考👉<a target="_blank" rel="noopener" href="https://www.bilibili.com/video/BV1Pf4y1B7XK">一个视频教会你算法的时间复杂度</a> || <a target="_blank" rel="noopener" href="https://www.bilibili.com/video/BV1fh411X7Jv">一个视频教会你算法的空间复杂度</a></p>
</div>
<h2 id="时间复杂度"><a href="#时间复杂度" class="headerlink" title="时间复杂度"></a>时间复杂度</h2><ul>
<li><strong>时间复杂度</strong><br>  算法的执行效率，算法的<strong>执行时间</strong>与算法<strong>的输入值</strong>之间的关系</li>
<li>以下例子，设语句执行时间为a,b,c，假设循环10次，则此代码的执行时间为a+10b+c，通常省略成10b，为nb，b为系数可以省略不计，所以时间复杂度为<code>O(n)</code></li>
</ul>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">funtion <span class="function"><span class="title">ON</span>(<span class="params">num</span>)</span>&#123;</span><br><span class="line">   <span class="keyword">var</span> total = <span class="number">0</span>;   <span class="comment">//a</span></span><br><span class="line">   <span class="function"><span class="title">fot</span>(<span class="params"><span class="keyword">var</span> i=<span class="number">0</span>;i&lt;num;i++</span>)</span>&#123;</span><br><span class="line">      total += i;  <span class="comment">//b</span></span><br><span class="line">   &#125;</span><br><span class="line">   <span class="keyword">return</span> total;   <span class="comment">//c</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<ul>
<li>以下代码，a+b都是常数，与输入num无关，所以时间复杂度为<code>O(1)</code></li>
</ul>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">O1</span>(<span class="params">num</span>)</span>&#123;</span><br><span class="line">   <span class="keyword">var</span> i=num;   <span class="comment">//a</span></span><br><span class="line">   <span class="keyword">var</span> j=num*<span class="number">2</span>;  <span class="comment">//b</span></span><br><span class="line">   <span class="keyword">return</span> i+j;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<ul>
<li>以下代码，while循环logN次，时间复杂度为<code>O(logN)</code></li>
</ul>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">OlogN</span>(<span class="params">num</span>)</span>&#123;</span><br><span class="line">   <span class="keyword">var</span> i=<span class="number">1</span>;</span><br><span class="line">   <span class="function"><span class="title">while</span>(<span class="params">i&lt;num</span>)</span>&#123;  <span class="comment">//num=N</span></span><br><span class="line">      i = i*<span class="number">2</span>;  <span class="comment">// N*a</span></span><br><span class="line">   &#125;</span><br><span class="line">   <span class="keyword">return</span> i;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<ul>
<li>以下代码，外层循环m次，内层循环了alogN次，去掉常数系数，则时间复杂度为<code>O(MlogN)</code></li>
</ul>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">ONLogN</span>(<span class="params">num1,num2</span>)</span>&#123;</span><br><span class="line">   <span class="keyword">var</span> total = <span class="number">0</span>;</span><br><span class="line">   <span class="keyword">var</span> j = <span class="number">0</span>;</span><br><span class="line">   <span class="function"><span class="title">for</span>(<span class="params"><span class="keyword">var</span> i=<span class="number">0</span>;i&lt;num1;i++</span>)</span>&#123; <span class="comment">//num1=m</span></span><br><span class="line">      <span class="function"><span class="title">while</span>(<span class="params">j &lt; num2</span>)</span>&#123;   <span class="comment">//num2=n</span></span><br><span class="line">      <span class="comment">//以下两个语言时间为a</span></span><br><span class="line">         total += i + j;</span><br><span class="line">         j = j*<span class="number">2</span>;</span><br><span class="line">      &#125;</span><br><span class="line">   &#125;</span><br><span class="line">   <span class="keyword">return</span> total;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


<ul>
<li>下列代码，并列两个循环，执行时间Mb+Nc，去掉固定常数，则时间复杂度为<code>O(M+N)</code></li>
</ul>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">OMN</span>(<span class="params">num1,num2</span>)</span>&#123;</span><br><span class="line">   <span class="keyword">var</span> total = <span class="number">0</span>;</span><br><span class="line">   <span class="function"><span class="title">for</span>(<span class="params"><span class="keyword">var</span> i=<span class="number">0</span>;i&lt;num1;i++</span>)</span>&#123; <span class="comment">//num1=M</span></span><br><span class="line">      total += i;   <span class="comment">//b -&gt; M*b</span></span><br><span class="line">   &#125;</span><br><span class="line">   <span class="function"><span class="title">for</span>(<span class="params"><span class="keyword">var</span> j=<span class="number">0</span>;j&lt;num2;j++</span>)</span>&#123;  <span class="comment">//num2=N</span></span><br><span class="line">      total += j;   <span class="comment">//c -&gt; N*c</span></span><br><span class="line">   &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<ul>
<li>以下代码，外层执行N次，内存执行aN次，去掉常数系数，则时间复杂度O(N<sup>2</sup>)</li>
</ul>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">ON2</span>(<span class="params">num</span>)</span>&#123;</span><br><span class="line">   <span class="keyword">var</span> total = <span class="number">0</span>;</span><br><span class="line">   <span class="function"><span class="title">for</span>(<span class="params"><span class="keyword">var</span> i=<span class="number">0</span>;i&lt;num;i++</span>)</span>&#123; <span class="comment">//num=N</span></span><br><span class="line">      <span class="function"><span class="title">for</span>(<span class="params"><span class="keyword">var</span> j=<span class="number">0</span>;j&lt;num;j++</span>)</span>&#123;</span><br><span class="line">         total += i + j; <span class="comment">//a</span></span><br><span class="line">      &#125;</span><br><span class="line">   &#125;</span><br><span class="line">   <span class="keyword">return</span> total;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<ul>
<li>对比</li>
</ul>
<p><img src="https://cdn.jsdelivr.net/gh/xiaoliblog/image@b157722136dab271f251860d0d2ed47ba982796f/2021/03/07/422445288095bd89804d2e0fc7c2ce06.png"></p>
<div class="note success simple"><p>O(1)&lt;O(logN)&lt;O(N)&lt;O(MlogN)&lt;O(n<sup>2</sup>)&lt;O(2<sup>n</sup>)&lt;O(n!)</p>
</div>

<h2 id="空间复杂度"><a href="#空间复杂度" class="headerlink" title="空间复杂度"></a>空间复杂度</h2><ul>
<li><p><strong>空间复杂度</strong><br>  算法的<strong>存储空间</strong>与<strong>输入值</strong>之间的关系</p>
</li>
<li><p>以下代码，定义一个整型变量为4个字节，是不变的，空间复杂度为<code>O(1)</code></p>
</li>
</ul>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">funtion <span class="function"><span class="title">test</span>(<span class="params">num</span>)</span>&#123;</span><br><span class="line">   <span class="keyword">var</span> total = <span class="number">0</span>;  </span><br><span class="line">   <span class="function"><span class="title">fot</span>(<span class="params"><span class="keyword">var</span> i=<span class="number">0</span>;i&lt;num;i++</span>)</span>&#123;</span><br><span class="line">      total += i;  </span><br><span class="line">   &#125;</span><br><span class="line">   <span class="keyword">return</span> total;   </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<ul>
<li>以下代码，定义一个整型数组，每一个元素所占4个字节，数组大小随参数nums变化，则所占空间为<code>nums*4</code>，则空间复杂度为<code>O(n)</code></li>
</ul>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">test</span>(<span class="params">nums</span>)</span>&#123;</span><br><span class="line">   <span class="keyword">var</span> array[];</span><br><span class="line">   <span class="function"><span class="title">for</span>(<span class="params"><span class="keyword">var</span> i=<span class="number">0</span>;i&lt;nums;i++</span>)</span>&#123;</span><br><span class="line">      array.append(i);</span><br><span class="line">   &#125;</span><br><span class="line">   <span class="keyword">return</span> array;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


<h1 id="两数之和"><a href="#两数之和" class="headerlink" title="两数之和"></a>两数之和</h1><ul>
<li>题目：给定一个整数数组<code> nums</code> 和一个目标值 <code>target</code>，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标</li>
<li>你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍</li>
<li>你可以按任意顺序返回答案</li>
<li>官方解题答案：<a target="_blank" rel="noopener" href="https://leetcode-cn.com/articles/two-sum/">https://leetcode-cn.com/articles/two-sum/</a></li>
</ul>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">输入：nums &#x3D; [2,7,11,15], target &#x3D; 9</span><br><span class="line">输出：[0,1]</span><br><span class="line">解释：因为 nums[0] + nums[1] &#x3D;&#x3D; 9 ，返回 [0, 1] </span><br></pre></td></tr></table></figure>

<h2 id="暴力法"><a href="#暴力法" class="headerlink" title="暴力法"></a>暴力法</h2><ul>
<li>两个两个一组，双层循环遍历所有可能，判断之和是否相等，即可找出答案，比如找到数组第一个数和后面所有的数两两相加判断是否等于目标值；</li>
<li>执行用68ms，内存消耗38.3MB</li>
</ul>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">var</span> twoSum = <span class="function"><span class="keyword">function</span>(<span class="params">nums, target</span>) </span>&#123;</span><br><span class="line">    <span class="function"><span class="title">for</span>(<span class="params"><span class="keyword">var</span> i=<span class="number">0</span>;i&lt;nums.length;i++</span>)</span>&#123;</span><br><span class="line">        <span class="function"><span class="title">for</span>(<span class="params"><span class="keyword">var</span> j=i+<span class="number">1</span>;j&lt;nums.length;j++</span>)</span>&#123;</span><br><span class="line">            <span class="function"><span class="title">if</span>(<span class="params">nums[i]+nums[j]==target</span>)</span>&#123;</span><br><span class="line">                <span class="keyword">return</span> [i,j];</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h2 id="哈希表法"><a href="#哈希表法" class="headerlink" title="哈希表法"></a>哈希表法</h2><ul>
<li>首先构造哈希表map，哈希表是一种<code>key:value</code>的数据结构，用来存放数组的值和索引</li>
<li>遍历数组 nums，i 为当前下标，每个值都判断map中是否存在 <code>target-nums[i]</code> 的 key 值，也就是给定值的另一半数字，比如9-2=7，查看map.key是否存在数字7</li>
<li>如果存在则找到了两个值并判断索引不相等，如果不存在则将当前的 (nums[i],i) 存入 map 中，继续遍历直到找到为止</li>
</ul>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">var</span> twoSum = <span class="function"><span class="keyword">function</span>(<span class="params">nums, target</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">var</span> map=<span class="keyword">new</span> <span class="built_in">Map</span>(); <span class="comment">//构造哈希表</span></span><br><span class="line">    <span class="function"><span class="title">for</span>(<span class="params"><span class="keyword">var</span> i = <span class="number">0</span>; i&lt; nums.length; i++</span>)</span> &#123; <span class="comment">//遍历</span></span><br><span class="line">        <span class="function"><span class="title">if</span>(<span class="params">map.has(target - nums[i])</span>)</span> &#123;  <span class="comment">//查看是否存在目标值的另一个数字</span></span><br><span class="line">                <span class="keyword">return</span> [map.get(target-nums[i]),i]; <span class="comment">//返回下标</span></span><br><span class="line">            &#125;</span><br><span class="line">            map.set(nums[i], i); <span class="comment">//不存在就放入哈希表</span></span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br></pre></td></tr></table></figure>

<div class="note success simple"><p><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/two-sum/solution/jie-suan-fa-1-liang-shu-zhi-he-by-guanpengchn/">动画演示地址</a></p>
</div>

<h1 id="两数相加"><a href="#两数相加" class="headerlink" title="两数相加"></a>两数相加</h1><ul>
<li>给你两个<strong>非空</strong>的链表，表示两个非负的整数。它们每位数字都是按照<strong>逆序</strong>的方式存储的，并且每个节点只能存储<strong>一位</strong> 数字，如果为两位数，取个位数并向后一位数进一</li>
<li>请你将两个数相加，并以相同形式返回一个表示和的链表</li>
<li>你可以假设除了数字 0 之外，这两个数都不会以 0 开头</li>
<li>例如6+4=10，取个位数0并进一，4+3=7加上进的一位为7+1=8<img src="https://cdn.jsdelivr.net/gh/xiaoliblog/image@0dbfa11fd5eb8995efb54f8970c83cf080359837/2021/02/26/e3aa908dfc61b4a23c93fdaec789431c.png"></li>
<li>官方解题答案：<a target="_blank" rel="noopener" href="https://leetcode-cn.com/articles/add-two-numbers/">https://leetcode-cn.com/articles/add-two-numbers/</a></li>
</ul>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">输入：l1 &#x3D; [2,4,3], l2 &#x3D; [5,6,4]</span><br><span class="line">输出：[7,0,8]</span><br><span class="line">解释：342 + 465 &#x3D; 807.</span><br><span class="line">&#x2F;&#x2F;极端进位清空</span><br><span class="line">输入：l1 &#x3D; [9,9,9], l2 &#x3D; [9,9]</span><br><span class="line">输出：[8,9,0,1]</span><br><span class="line">解释：999+99&#x3D;1098</span><br></pre></td></tr></table></figure>

<h2 id="解题思路"><a href="#解题思路" class="headerlink" title="解题思路"></a>解题思路</h2><ul>
<li><strong>除法运算</strong>除10可以得到十位上的数(<code>12/10=1</code>)，对10<strong>取余运算</strong>可以得到个位数(<code>12%10=2</code>)</li>
<li>使用变量<code>carry</code>标记下一个数进位多少，并从包含最低有效位的表头开始模拟逐位相加的过程<img src="https://cdn.jsdelivr.net/gh/xiaoliblog/image@0dbfa11fd5eb8995efb54f8970c83cf080359837/2021/02/26/e3aa908dfc61b4a23c93fdaec789431c.png"></li>
<li>例如，5 + 7 = 12在这种情况下，我们会将当前位的数值设置为 2，并将进位 <code>carry = 1</code>带入下一次迭代。<strong>进位 carry必定是 0 或 1</strong>，这是因为两个数字相加（考虑到进位）可能出现的最大和为 9 + 9 + 1 = 19</li>
<li>算法思路如下<ol>
<li>创建一个<code>dummy</code>头结点，然后相加的结果依次添加串起来</li>
<li><code>curr</code>指针指向头结点，用于往后遍历，并将指向的当前结点初始化为返回链表的哑结点</li>
<li>将进位<code>carry</code>初始为0</li>
<li>遍历链表L1和L2直至到达它们的尾端<ul>
<li>设定<code>sum=l1.val+l2.val+carry</code></li>
<li>更新进位的值，<code>carry=sum/10</code></li>
<li>创建一个数值为(<code>sum%10</code>) 的新结点，并将其设置为当前结点的下一个结点，然后将当前结点前进到下一个结点</li>
<li>同时，将l1和l2前进到下一个结点</li>
</ul>
</li>
<li>检查最后<code> carry=1</code> 是否成立，如果成立，则向返回列表追加一个含有数字 1 的新结点</li>
<li>返回哑结点的下一个结点</li>
</ol>
</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * Definition for singly-linked list.</span></span><br><span class="line"><span class="comment"> * public class ListNode &#123;</span></span><br><span class="line"><span class="comment"> *     int val;</span></span><br><span class="line"><span class="comment"> *     ListNode next;</span></span><br><span class="line"><span class="comment"> *     ListNode() &#123;&#125;</span></span><br><span class="line"><span class="comment"> *     ListNode(int val) &#123; this.val = val; &#125;</span></span><br><span class="line"><span class="comment"> *     ListNode(int val, ListNode next) &#123; this.val = val; this.next = next; &#125;</span></span><br><span class="line"><span class="comment"> * &#125;</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"> <span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> ListNode <span class="title">addTwoNumbers</span><span class="params">(ListNode l1, ListNode l2)</span> </span>&#123;</span><br><span class="line">        ListNode doummy = <span class="keyword">new</span> ListNode(<span class="number">0</span>);  <span class="comment">//初始一个返回链表的头结点</span></span><br><span class="line">        ListNode curr = doummy; <span class="comment">//curr指针用来遍历链表</span></span><br><span class="line">        <span class="keyword">int</span> carry=<span class="number">0</span>; <span class="comment">//定义进位变量，无进位为0，有进位为1</span></span><br><span class="line">        <span class="keyword">while</span>( l1 != <span class="keyword">null</span> || l2 != <span class="keyword">null</span>)&#123;  <span class="comment">//两个链表都不为空</span></span><br><span class="line">            <span class="keyword">int</span> sum=<span class="number">0</span>;</span><br><span class="line">            <span class="keyword">if</span>( l1 != <span class="keyword">null</span>)&#123;</span><br><span class="line">                sum += l1.val; <span class="comment">//求和</span></span><br><span class="line">                l1 = l1.next;  <span class="comment">//移到下一位</span></span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span>( l2 != <span class="keyword">null</span>)&#123;</span><br><span class="line">                sum += l2.val; <span class="comment">//求和</span></span><br><span class="line">                l2 = l2.next;  <span class="comment">//移到下一位</span></span><br><span class="line">            &#125;</span><br><span class="line">            sum += carry; <span class="comment">//再加上carry进位的值</span></span><br><span class="line">            curr.next=<span class="keyword">new</span> ListNode(sum%<span class="number">10</span>); <span class="comment">//取个位上的数作为新结点加到当前指向的结点后面</span></span><br><span class="line">            carry = sum/<span class="number">10</span>;   <span class="comment">//计算是否进位</span></span><br><span class="line">            curr = curr.next;  <span class="comment">//遍历指针移动到下一位</span></span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span>(carry&gt;<span class="number">0</span>)&#123;   <span class="comment">//判断最后carry进位是否为1</span></span><br><span class="line">            curr.next = <span class="keyword">new</span> ListNode(carry);  <span class="comment">//如果为1，就作为结点加到后面</span></span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> doummy.next; <span class="comment">//返回结果链表</span></span><br><span class="line">        &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<div class="note success simple"><p><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/add-two-numbers/solution/hua-jie-suan-fa-2-liang-shu-xiang-jia-by-guanpengc/">动画演示地址</a></p>
</div>

<h1 id="无重复字符的最长子串"><a href="#无重复字符的最长子串" class="headerlink" title="无重复字符的最长子串"></a>无重复字符的最长子串</h1><ul>
<li>给定一个字符串，请你找出其中不含有重复字符的<strong>最长子串</strong>的长度</li>
<li>官方解题答案：<a target="_blank" rel="noopener" href="https://leetcode-cn.com/articles/longest-substring-without-repeating-characters/">https://leetcode-cn.com/articles/longest-substring-without-repeating-characters/</a></li>
</ul>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">输入: s &#x3D; &quot;abcabcbb&quot;</span><br><span class="line">输出: 3 </span><br><span class="line">解释: 因为无重复字符的最长子串是 &quot;abc&quot;，因为往后会遇到a，a会重复，所以其长度为 3。</span><br><span class="line">-----</span><br><span class="line">输入: s &#x3D; &quot;pwwkew&quot;</span><br><span class="line">输出: 3</span><br><span class="line">解释: 因为无重复字符的最长子串是 &quot;wke&quot;，所以其长度为 3。</span><br><span class="line"> 请注意，你的答案必须是子串的长度，&quot;pwke&quot; 是一个子序列，不是子串。&quot;pw&quot;也不是，因为不是最长</span><br></pre></td></tr></table></figure>

<h2 id="滑动窗口"><a href="#滑动窗口" class="headerlink" title="滑动窗口"></a>滑动窗口</h2><ul>
<li><strong>滑动窗口sliding window</strong><br>  其实就是一个队列，比如例题中的 <code>abcabcbb</code>，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！</li>
<li>如何移动？<br>  我们只要把队列的左边的元素移出就行了，直到满足题目要求！一直维持这样的队列，找出队列出现最长的长度时候，求出解！</li>
<li>算法思路<ol>
<li>创建一个<code>set</code></li>
<li>两个指针，第一个指向字符串的开头<code>j</code>，第二个随着for循环遍历字符串<code>i</code></li>
<li>如果<code>set</code>里没有<code>s[i]</code>， 说明目前为止还没有重复的字符,把s[i]添加到set里，然后更新最大不重复字符的数量，用<code>maxLength</code>变量存储，如果<code>maxLength&lt;set.size</code>就更新，否则不更新</li>
<li>如果set里有s[i]，则从set里开始<strong>删除</strong>s[j]，并且递增，再检查set里是否有s[i]，如此反复直到set里没有s[i]为止</li>
<li>重复步骤3和4，直到遍历完整个字符串<img src="https://cdn.jsdelivr.net/gh/xiaoliblog/image@9c07f8059cfd0caf7405aec9c70596d2b4656663/2021/03/06/c411f603105fbc21bc01dc6dff8a67b2.png"></li>
</ol>
</li>
</ul>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;string&#125;</span> <span class="variable">s</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;number&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> lengthOfLongestSubstring = <span class="function"><span class="keyword">function</span>(<span class="params">s</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">const</span> set = <span class="keyword">new</span> <span class="built_in">Set</span>(); <span class="comment">//创建一个set集合</span></span><br><span class="line">    <span class="keyword">let</span> i = <span class="number">0</span>,j = <span class="number">0</span>,maxLength = <span class="number">0</span>; <span class="comment">//创建两个指针和记录最大不重复字符数量的变量</span></span><br><span class="line">    <span class="function"><span class="title">if</span>(<span class="params">s.length === <span class="number">0</span></span>)</span>&#123;  <span class="comment">//字符串为空</span></span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function"><span class="title">for</span>(<span class="params">i;i&lt;s.length;i++</span>)</span>&#123;  <span class="comment">//遍历字符串</span></span><br><span class="line">        <span class="function"><span class="title">if</span>(<span class="params"> ! set.has(s[i])</span>)</span>&#123; <span class="comment">//不重复情况，即set里没有s[i]，则添加到set里</span></span><br><span class="line">            set.add(s[i]);</span><br><span class="line">            maxLength = <span class="built_in">Math</span>.max(maxLength,set.size); <span class="comment">//更新maxLength的值，保证为最大值</span></span><br><span class="line">        &#125;<span class="keyword">else</span>&#123; <span class="comment">//出现重复情况</span></span><br><span class="line">            <span class="function"><span class="title">while</span>(<span class="params">set.has(s[i])</span>)</span>&#123; <span class="comment">//如果set里有s[i]，则从set里开始删除s[j]</span></span><br><span class="line">                set.delete(s[j]);</span><br><span class="line">                j++;   <span class="comment">//j后移一位</span></span><br><span class="line">            &#125;</span><br><span class="line">            set.add(s[i]);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">     <span class="keyword">return</span> maxLength;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<div class="note success simple"><p><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/hua-jie-suan-fa-3-wu-zhong-fu-zi-fu-de-zui-chang-z/">动画演示</a></p>
</div>

<h1 id="最长回文子串"><a href="#最长回文子串" class="headerlink" title="最长回文子串"></a>最长回文子串</h1><ul>
<li>给你一个字符串 s，找到 s 中最长的回文子串，即一个字符串正序和逆序都是一样的</li>
</ul>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line">输入：s &#x3D; &quot;babad&quot;</span><br><span class="line">输出：&quot;bab&quot;</span><br><span class="line">解释：&quot;aba&quot; 同样是符合题意的答案</span><br><span class="line">---</span><br><span class="line">输入：s &#x3D; &quot;ac&quot;</span><br><span class="line">输出：&quot;a&quot;</span><br></pre></td></tr></table></figure>

<ul>
<li>采用<strong>从中心向两边扩散</strong>的方法，例如<code>babad</code>，但不是每个字符串都有中心点，例如<code>cabbad</code></li>
<li>算法思路<ol>
<li>如果字符串长度<strong>小于2</strong>，直接返回原字符串</li>
<li>定义两个变量，一个<code>start</code>存储当前找到的最大回文字符串的起始位置，另一个<code>maxLength</code>记录字符串的长度(终止位置就是<code>start+ maxLength</code>)</li>
<li>创建一个<code>helper function</code>，判断左边和右边是否越界，同时最左边的字符是否等于最右边的字符。如果以上三个条件都满足，则判断是否需要更新回文字符串最大长度及最大字符串的起始位置。然后将<code>left--</code>，<code>right++</code>向两边扩散，继续判断，直到不满足三个条件之一。</li>
<li>遍历字符串，每个位置调用<code>helper function</code>两遍，第一遍检查<code>i-1</code>,<code>i+1</code>, 第二遍检查<code>i</code>;<code>i+1</code>，第一遍查询处理存在中心的情况(babad)，第二遍查询处理不存在中心的情况(cabbad)</li>
</ol>
</li>
</ul>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;string&#125;</span> <span class="variable">s</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;string&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> longestPalindrome = <span class="function"><span class="keyword">function</span>(<span class="params">s</span>) </span>&#123;</span><br><span class="line">    <span class="function"><span class="title">if</span>(<span class="params">s.length &lt; <span class="number">2</span></span>)</span>&#123;</span><br><span class="line">        <span class="keyword">return</span> s;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">let</span> start = <span class="number">0</span>; <span class="comment">//存储当前找到的最大回文字符串的起始位置</span></span><br><span class="line">    <span class="keyword">let</span> maxLength = <span class="number">1</span>; <span class="comment">//记录字符串的长度</span></span><br><span class="line">    <span class="function"><span class="keyword">function</span> <span class="title">expandAroundCenter</span>(<span class="params">left,right</span>)</span>&#123; <span class="comment">//helper function函数</span></span><br><span class="line">        <span class="function"><span class="title">while</span>(<span class="params">left &gt;= <span class="number">0</span> &amp;&amp; right &lt;= s.length-<span class="number">1</span> &amp;&amp; s[left] === s[right]</span>)</span>&#123;</span><br><span class="line">            <span class="function"><span class="title">if</span>(<span class="params">right - left + <span class="number">1</span> &gt; maxLength</span>)</span>&#123; <span class="comment">//找到更大的回文字符串</span></span><br><span class="line">                maxLength = right - left +<span class="number">1</span>;</span><br><span class="line">                start = left;</span><br><span class="line">            &#125; </span><br><span class="line">            <span class="comment">//向两边扩散</span></span><br><span class="line">            left --;</span><br><span class="line">            right ++;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function"><span class="title">for</span>(<span class="params"><span class="keyword">let</span> i = <span class="number">0</span>;i &lt; s.length; i ++ </span>)</span>&#123; <span class="comment">//每个元素都当作中心调用函数</span></span><br><span class="line">        expandAroundCenter(i-<span class="number">1</span>,i+<span class="number">1</span>);</span><br><span class="line">        expandAroundCenter(i,i+<span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> s.substring(start,start+maxLength); <span class="comment">//截取字符串</span></span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h1 id="三数之和"><a href="#三数之和" class="headerlink" title="三数之和"></a>三数之和</h1><ul>
<li>给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 <code>a + b + c = 0</code> ？请你找出所有和为 0 且不重复的三元组</li>
<li>注意：答案中不可以包含重复的三元组</li>
</ul>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">输入：nums &#x3D; [-1,0,1,2,-1,-4]</span><br><span class="line">输出：[[-1,-1,2],[-1,0,1]]</span><br><span class="line">--- </span><br><span class="line">输入：nums &#x3D; [0]</span><br><span class="line">输出：[]</span><br></pre></td></tr></table></figure>

<ul>
<li>算法思路<ol>
<li>给数组排序</li>
<li>遍历数组，从0遍历到小于<code>length-2</code> ，<strong>防止越界</strong></li>
<li>如果当前的数字等于前一个数字，则跳过这个数，<strong>去掉重复</strong></li>
<li>如果数字不同，则设置<code>start= i+1</code>，<code>end=length-1</code>，查看<code>i</code>，<code>start</code>和<code>end</code>三个数的和此零大还是小，如果比0小，<code>start++</code>，如果比0大，<code>end--</code>，如果等于0，把这三个数加入到结果里。</li>
<li>返回结果</li>
</ol>
</li>
</ul>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number[]&#125;</span> <span class="variable">nums</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;number[][]&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> threeSum = <span class="function"><span class="keyword">function</span> (<span class="params">nums</span>) </span>&#123;</span><br><span class="line">  <span class="keyword">const</span> result = [];   <span class="comment">//存放结果</span></span><br><span class="line">  nums.sort(<span class="function"><span class="keyword">function</span> (<span class="params">a, b</span>) </span>&#123; <span class="comment">//数组排序</span></span><br><span class="line">    <span class="keyword">return</span> a - b;</span><br><span class="line">  &#125;);</span><br><span class="line"></span><br><span class="line">  <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; nums.length - <span class="number">2</span>; i++) &#123;  <span class="comment">//遍历数组至length-2，防止越界</span></span><br><span class="line">    <span class="keyword">if</span> (i === <span class="number">0</span> || nums[i] !== nums[i - <span class="number">1</span>]) &#123; <span class="comment">//去重操作，重复就跳过</span></span><br><span class="line">      <span class="keyword">let</span> start = i + <span class="number">1</span>; </span><br><span class="line">      <span class="keyword">let</span> end = nums.length - <span class="number">1</span>;</span><br><span class="line">      <span class="keyword">while</span> (start &lt; end) &#123;  <span class="comment">//两边指针向里面缩</span></span><br><span class="line">        <span class="keyword">if</span> (nums[i] + nums[start] + nums[end] === <span class="number">0</span>) &#123;  <span class="comment">//找到正确结果</span></span><br><span class="line">          result.push([nums[i], nums[start], nums[end]]); <span class="comment">//存放到result数组里</span></span><br><span class="line">          start++;</span><br><span class="line">          end--;</span><br><span class="line">          <span class="comment">//去重操作</span></span><br><span class="line">          <span class="keyword">while</span> (start &lt; end &amp;&amp; nums[start] === nums[start - <span class="number">1</span>]) &#123;</span><br><span class="line">            start++;</span><br><span class="line">          &#125;</span><br><span class="line">          <span class="keyword">while</span> (start &lt; end &amp;&amp; nums[end] === nums[end + <span class="number">1</span>]) &#123;</span><br><span class="line">            end--;</span><br><span class="line">          &#125;</span><br><span class="line">        &#125; <span class="keyword">else</span> <span class="keyword">if</span> (nums[i] + nums[start] + nums[end] &lt; <span class="number">0</span>) &#123;</span><br><span class="line">          start++;</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">          end--;</span><br><span class="line">        &#125;</span><br><span class="line">      &#125;</span><br><span class="line">    &#125;</span><br><span class="line">  &#125;</span><br><span class="line"></span><br><span class="line">  <span class="keyword">return</span> result;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<div class="note success simple"><p><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/3sum/solution/hua-jie-suan-fa-15-san-shu-zhi-he-by-guanpengchn/">算法演示</a></p>
</div></article><div class="post-copyright"><div class="post-copyright__author"><span class="post-copyright-meta">文章作者: </span><span class="post-copyright-info"><a href="mailto:undefined">小李博客</a></span></div><div class="post-copyright__type"><span class="post-copyright-meta">文章链接: </span><span class="post-copyright-info"><a href="https://xiaoliblog.cn">https://xiaoliblog.cn</a></span></div><div class="post-copyright__notice"><span class="post-copyright-meta">版权声明: </span><span class="post-copyright-info">本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" target="_blank">CC BY-NC-SA 4.0</a> 许可协议。转载请注明来自 <a href="http://xiaoliblog.cn" target="_blank">小李博客</a>！</span></div></div><div class="tag_share"><div class="post-meta__tag-list"><a class="post-meta__tags" href="/tags/LeetCode/">LeetCode</a></div><div class="post_share"><div class="social-share" data-image="https://cdn.jsdelivr.net/gh/xiaoliblog/image@efa02577d8e4f5d49ebb4bd77f5647822d901ed8/2021/01/24/d99d6d32543e0965b25ee42a87ab34a9.png" data-sites="facebook,twitter,wechat,weibo,qq"></div><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/social-share.js/dist/css/share.min.css" media="print" onload="this.media='all'"><script src="https://cdn.jsdelivr.net/npm/social-share.js/dist/js/social-share.min.js" defer></script></div></div><div class="post-reward"><div class="reward-button button--animated"><i class="fas fa-qrcode"></i> 打赏</div><div class="reward-main"><ul class="reward-all"><li class="reward-item"><a href="/img/wechat.png" target="_blank"><img class="post-qr-code-img" src="/img/wechat.png" alt="微信"/></a><div class="post-qr-code-desc">微信</div></li><li class="reward-item"><a href="/img/alipay.png" target="_blank"><img class="post-qr-code-img" src="/img/alipay.png" alt="支付宝"/></a><div class="post-qr-code-desc">支付宝</div></li></ul></div></div><nav class="pagination-post" id="pagination"><div class="prev-post pull-left"><a href="/page/markdown.html"><img class="prev-cover" src="https://cdn.jsdelivr.net/gh/xiaoliblog/image@a9ea9d3fad21a25c3594e296b2e955d3d96905a0/2021/01/24/2cd19ef188f4e3cf9b98c80bf695e40e.png" onerror="onerror=null;src='https://cdn.jsdelivr.net/gh/lzyblog/image@main/2020/11/19/bd16b394f7359083b1f6072a67e3f968.png'" alt="cover of previous post"><div class="pagination-info"><div class="label">上一篇</div><div class="prev_info">Markdown语法</div></div></a></div><div class="next-post pull-right"><a href="/page/hexoblog.html"><img class="next-cover" src="https://cdn.jsdelivr.net/gh/xiaoliblog/image@88d6104165d7beac0f2c2844a539c0feffa4f33d/2021/01/24/993832d0c82e0ea4f5f7d61fb74320a6.png" onerror="onerror=null;src='https://cdn.jsdelivr.net/gh/lzyblog/image@main/2020/11/19/bd16b394f7359083b1f6072a67e3f968.png'" alt="cover of next post"><div class="pagination-info"><div class="label">下一篇</div><div class="next_info">Hexo+GitHub搭建个人博客</div></div></a></div></nav><hr/><div id="post-comment"><div class="comment-head"><div class="comment-headline"><i class="fas fa-comments fa-fw"></i><span> 评论</span></div></div><div class="comment-wrap"><div><div id="twikoo-wrap"></div></div></div></div></div><div class="aside-content" id="aside-content"><div class="card-widget card-info"><div class="card-info-avatar is-center"><img class="avatar-img" src="https://cdn.jsdelivr.net/gh/xiaoliblog/image@6b5e7ef72be1c8973d94e5a9c49accbf775ad820/2021/02/01/c485da031fe0e464d04eaba8a66c4a8f.png" onerror="this.onerror=null;this.src='/img/friend_404.gif'" alt="avatar"/><div class="author-info__name">小李博客</div><div class="author-info__description">越努力，越幸运！</div></div><div class="card-info-data"><div class="card-info-data-item is-center"><a href="/archives/"><div class="headline">文章</div><div class="length-num">210</div></a></div><div class="card-info-data-item is-center"><a href="/tags/"><div class="headline">标签</div><div class="length-num">38</div></a></div><div class="card-info-data-item is-center"><a href="/categories/"><div class="headline">分类</div><div class="length-num">56</div></a></div></div><a class="button--animated" id="card-info-btn" target="_blank" rel="noopener" href="https://github.com/xiaoliblog"><i class="fab fa-github"></i><span>博主的GitHub首页</span></a><div class="card-info-social-icons is-center"><a class="social-icon" href="https://gitee.com/xiaoliblog" target="_blank" title="Gitee"><i class="iconfont icon-gitee card_icon_gitee"></i></a><a class="social-icon" href="https://space.bilibili.com/390969485" target="_blank" title="BiliBili"><i class="iconfont icon-bilibili card_icon_bilibili"></i></a><a class="social-icon" href="http://wpa.qq.com/msgrd?v=3&amp;uin=2312057536&amp;site=CSDN&amp;menu=yes" target="_blank" title="QQ"><i class="iconfont icon-qq card_icon_qq"></i></a><a class="social-icon" href="https://github.com/xiaoliblog" target="_blank" title="GitHub"><i class="iconfont icon-git card_icon_git"></i></a><a class="social-icon" href="https://blog.csdn.net/qq_43266250?spm=1010.2135.3001.5113" target="_blank" title="CSDN"><i class="iconfont icon-csdn card_icon_csdn"></i></a></div></div><div class="card-widget card-announcement"><div class="item-headline"><i class="fas fa-bullhorn card-announcement-animation"></i><span>公告</span></div><div class="announcement_content">正在考研备考中💦</div></div><div class="sticky_layout"><div class="card-widget" id="card-toc"><div class="item-headline"><i class="fas fa-stream"></i><span>目录</span></div><div class="toc-content"><ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#%E5%8F%82%E8%80%83"><span class="toc-number">1.</span> <span class="toc-text">参考</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E7%AE%97%E6%B3%95%E6%80%A7%E8%83%BD%E5%88%86%E6%9E%90"><span class="toc-number">2.</span> <span class="toc-text">算法性能分析</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6"><span class="toc-number">2.1.</span> <span class="toc-text">时间复杂度</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%A9%BA%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6"><span class="toc-number">2.2.</span> <span class="toc-text">空间复杂度</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8C"><span class="toc-number">3.</span> <span class="toc-text">两数之和</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%9A%B4%E5%8A%9B%E6%B3%95"><span class="toc-number">3.1.</span> <span class="toc-text">暴力法</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%93%88%E5%B8%8C%E8%A1%A8%E6%B3%95"><span class="toc-number">3.2.</span> <span class="toc-text">哈希表法</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E4%B8%A4%E6%95%B0%E7%9B%B8%E5%8A%A0"><span class="toc-number">4.</span> <span class="toc-text">两数相加</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="toc-number">4.1.</span> <span class="toc-text">解题思路</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E6%97%A0%E9%87%8D%E5%A4%8D%E5%AD%97%E7%AC%A6%E7%9A%84%E6%9C%80%E9%95%BF%E5%AD%90%E4%B8%B2"><span class="toc-number">5.</span> <span class="toc-text">无重复字符的最长子串</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3"><span class="toc-number">5.1.</span> <span class="toc-text">滑动窗口</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E6%9C%80%E9%95%BF%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2"><span class="toc-number">6.</span> <span class="toc-text">最长回文子串</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E4%B8%89%E6%95%B0%E4%B9%8B%E5%92%8C"><span class="toc-number">7.</span> <span class="toc-text">三数之和</span></a></li></ol></div></div><div class="card-widget card-recent-post"><div class="item-headline"><i class="fas fa-history"></i><span>最新文章</span></div><div class="aside-list"><div class="aside-list-item"><a class="thumbnail" href="/page/project01.html" title="前端实例🥳响应式网站首页"><img src="https://cdn.jsdelivr.net/gh/xiaoliblog/image@c19917500ab083c77c7613263ba7ee74d5a08ae6/2021/04/30/469f30b141d73fa0fc4c962662d5813f.png" onerror="this.onerror=null;this.src='https://cdn.jsdelivr.net/gh/lzyblog/image@main/2020/11/19/bd16b394f7359083b1f6072a67e3f968.png'" alt="前端实例🥳响应式网站首页"/></a><div class="content"><a class="title" href="/page/project01.html" title="前端实例🥳响应式网站首页">前端实例🥳响应式网站首页</a><time datetime="2021-04-30T11:50:53.094Z" title="发表于 2021-04-30 19:50:53">2021-04-30</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/page/WeChatpay.html" title="微信支付对接"><img src="https://cdn.jsdelivr.net/gh/xiaoliblog/image@f2f670b92ea149650ffa7834354fc90284f2f44a/2021/04/29/5bdc9b381a06193d27cf2fb7c2fb608a.png" onerror="this.onerror=null;this.src='https://cdn.jsdelivr.net/gh/lzyblog/image@main/2020/11/19/bd16b394f7359083b1f6072a67e3f968.png'" alt="微信支付对接"/></a><div class="content"><a class="title" href="/page/WeChatpay.html" title="微信支付对接">微信支付对接</a><time datetime="2021-04-29T12:20:48.070Z" title="发表于 2021-04-29 20:20:48">2021-04-29</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/page/Alipay.html" title="支付宝支付对接"><img src="https://cdn.jsdelivr.net/gh/xiaoliblog/image@61a9b6a6e09e4bda38bb08e3104b717885beaee5/2021/04/29/c3fa51f9cf14e90d9e5a7aa8814dd041.png" onerror="this.onerror=null;this.src='https://cdn.jsdelivr.net/gh/lzyblog/image@main/2020/11/19/bd16b394f7359083b1f6072a67e3f968.png'" alt="支付宝支付对接"/></a><div class="content"><a class="title" href="/page/Alipay.html" title="支付宝支付对接">支付宝支付对接</a><time datetime="2021-04-27T16:00:00.000Z" title="发表于 2021-04-28 00:00:00">2021-04-28</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/page/Vuejs11.html" title="Vue.js前端框架🎯Pagination+PageHelper实现分页"><img src="https://cdn.jsdelivr.net/gh/xiaoliblog/image@61bf4245f6d84d2d0f66d163b89c916788cc1845/2021/04/13/ec6b232f8fe5a840e4bd8c3eabcf49b2.png" onerror="this.onerror=null;this.src='https://cdn.jsdelivr.net/gh/lzyblog/image@main/2020/11/19/bd16b394f7359083b1f6072a67e3f968.png'" alt="Vue.js前端框架🎯Pagination+PageHelper实现分页"/></a><div class="content"><a class="title" href="/page/Vuejs11.html" title="Vue.js前端框架🎯Pagination+PageHelper实现分页">Vue.js前端框架🎯Pagination+PageHelper实现分页</a><time datetime="2021-04-26T14:48:39.701Z" title="发表于 2021-04-26 22:48:39">2021-04-26</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/page/Vuejs10.html" title="Vue.js前端框架🎯Vue-Element-admin模版"><img src="https://cdn.jsdelivr.net/gh/xiaoliblog/image@61bf4245f6d84d2d0f66d163b89c916788cc1845/2021/04/13/ec6b232f8fe5a840e4bd8c3eabcf49b2.png" onerror="this.onerror=null;this.src='https://cdn.jsdelivr.net/gh/lzyblog/image@main/2020/11/19/bd16b394f7359083b1f6072a67e3f968.png'" alt="Vue.js前端框架🎯Vue-Element-admin模版"/></a><div class="content"><a class="title" href="/page/Vuejs10.html" title="Vue.js前端框架🎯Vue-Element-admin模版">Vue.js前端框架🎯Vue-Element-admin模版</a><time datetime="2021-04-19T16:00:00.000Z" title="发表于 2021-04-20 00:00:00">2021-04-20</time></div></div></div></div></div></div></main><footer id="footer"><div id="footer-wrap"><div class="copyright">&copy;2020 - 2021 By 小李博客</div><div class="framework-info"><span>框架 </span><a target="_blank" rel="noopener" href="https://hexo.io">🎯Hexo</a><span class="footer-separator">|</span><span>主题 </span><a target="_blank" rel="noopener" href="https://github.com/jerryc127/hexo-theme-butterfly">🎉Butterfly</a></div><div class="footer_custom_text"><span><a style="margin-inline:5px" target="_blank" href="https://hexo.io/"><img src="https://img.shields.io/badge/Frame-Hexo-blue?style=flat&logo=hexo" title="博客框架为Hexo"></a><a style="margin-inline:5px" target="_blank" href="https://butterfly.js.org/"><img src="https://img.shields.io/badge/Theme-Butterfly-6513df?style=flat&logo=bitdefender" title="主题采用butterfly"></a><a style="margin-inline:5px" target="_blank" href="https://www.jsdelivr.com/"><img src="https://img.shields.io/badge/CDN-jsDelivr-orange?style=flat&logo=jsDelivr" title="本站使用JsDelivr为静态资源提供CDN加速"></a><a style="margin-inline:5px" target="_blank" href="https://vercel.com/ "><img src="https://img.shields.io/badge/Hosted-Vercel-brightgreen?style=flat&logo=Vercel" title="本站采用双线部署，默认线路托管于Vercel"></a><a style="margin-inline:5px" target="_blank" href="https://coding.net/ "><img src="https://img.shields.io/badge/Hosted-Coding-0cedbe?style=flat&logo=Codio" title="本站采用双线部署，联通线路托管于Coding"></a><a style="margin-inline:5px" target="_blank" href="https://github.com/"><img src="https://img.shields.io/badge/Source-Github-d021d6?style=flat&logo=GitHub" title="本站项目由Gtihub托管"></a><a style="margin-inline:5px" target="_blank" href="http://creativecommons.org/licenses/by-nc-sa/4.0/"><img src="https://img.shields.io/badge/Copyright-BY--NC--SA%204.0-d42328?style=flat&logo=Claris" title="本站采用知识共享署名-非商业性使用-相同方式共享4.0国际许可协议进行许可"></a></span></div><div class="icp"><a target="_blank" rel="noopener" href="https://beian.miit.gov.cn/"><img class="icp-icon" src="/img/icp.png" alt="ICP"/><span>湘ICP备2021002541号</span></a></div></div></footer></div><div id="rightside"><div id="rightside-config-hide"><button id="readmode" type="button" title="阅读模式"><i class="fas fa-book-open"></i></button><button id="font-plus" type="button" title="放大字体"><i class="fas fa-plus"></i></button><button id="font-minus" type="button" title="缩小字体"><i class="fas fa-minus"></i></button><button id="translateLink" type="button" title="简繁转换">繁</button><button id="darkmode" type="button" title="浅色和深色模式转换"><i class="fas fa-adjust"></i></button><button id="hide-aside-btn" type="button" title="单栏和双栏切换"><i class="fas fa-arrows-alt-h"></i></button></div><div id="rightside-config-show"><button id="rightside_config" type="button" title="设置"><i class="fas fa-cog fa-spin"></i></button><button class="close" id="mobile-toc-button" type="button" title="目录"><i class="fas fa-list-ul"></i></button><button id="chat_btn" type="button" title="rightside.chat_btn"><i class="fas fa-sms"></i></button><a id="to_comment" href="#post-comment" title="直达评论"><i class="fas fa-comments"></i></a><button id="go-up" type="button" title="回到顶部"><i class="fas fa-arrow-up"></i></button></div></div><div id="algolia-search"><div class="search-dialog"><div class="search-dialog__title" id="algolia-search-title">Algolia</div><div id="algolia-input-panel"><div id="algolia-search-input"></div></div><hr/><div id="algolia-search-results"><div id="algolia-hits"></div><div id="algolia-pagination"></div><div id="algolia-stats"></div></div><span class="search-close-button"><i class="fas fa-times"></i></span></div><div id="search-mask"></div></div><div><script src="/js/utils.js"></script><script src="https://cdn.jsdelivr.net/npm/vue@2.6.11"></script><script src="/js/main.js"></script><script defer src="/js/tw_cn.js"></script><script defer src="https://cdn.jsdelivr.net/npm/medium-zoom/dist/medium-zoom.min.js"></script><script src="https://cdn.jsdelivr.net/npm/instant.page/instantpage.min.js" type="module" defer></script><script defer src="https://cdn.jsdelivr.net/npm/node-snackbar/dist/snackbar.min.js"></script><script defer src="/js/search/algolia.js"></script><div class="js-pjax"><script>if (!window.MathJax) {
  window.MathJax = {
    loader: {
      source: {
        '[tex]/amsCd': '[tex]/amscd'
      }
    },
    tex: {
      inlineMath: [ ['$','$'], ["\\(","\\)"]],
      tags: 'ams'
    },
    options: {
      renderActions: {
        findScript: [10, doc => {
          for (const node of document.querySelectorAll('script[type^="math/tex"]')) {
            const display = !!node.type.match(/; *mode=display/)
            const math = new doc.options.MathItem(node.textContent, doc.inputJax[0], display)
            const text = document.createTextNode('')
            node.parentNode.replaceChild(text, node)
            math.start = {node: text, delim: '', n: 0}
            math.end = {node: text, delim: '', n: 0}
            doc.math.push(math)
          }
        }, ''],
        addClass: [200,() => {
          document.querySelectorAll('mjx-container:not([display=\'true\']').forEach( node => {
            const target = node.parentNode
            if (!target.classList.contains('has-jax')) {
              target.classList.add('mathjax-overflow')
            }
          })
        }, '', false]
      }
    }
  }
  
  const script = document.createElement('script')
  script.src = 'https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js'
  script.id = 'MathJax-script'
  script.async = true
  document.head.appendChild(script)
} else {
  MathJax.startup.document.state(0)
  MathJax.texReset()
  MathJax.typeset()
}</script><script>if (document.getElementsByClassName('mermaid').length) {
  if (window.mermaidJsLoad) mermaid.init()
  else {
    getScript('https://cdn.jsdelivr.net/npm/mermaid/dist/mermaid.min.js').then(() => {
      window.mermaidJsLoad = true
      mermaid.initialize({
        theme: 'default',
      })
      false && mermaid.init()
    })
  }
}</script><script>(()=>{
  const $countDom = document.getElementById('twikoo-count')
  const init = () => {
    twikoo.init(Object.assign({
      el: '#twikoo-wrap',
      envId: 'xiaoliblog-8gj3j5045d5b0896',
      region: ''
    }, null))
  }

  const getCount = () => {
    twikoo.getCommentsCount({
      envId: 'xiaoliblog-8gj3j5045d5b0896',
      region: '',
      urls: [window.location.pathname],
      includeReply: false
    }).then(function (res) {
      $countDom.innerText = res[0].count
    }).catch(function (err) {
      console.error(err);
    });
  }

  const loadTwikoo = (bool = false) => {
    if (typeof twikoo === 'object') {
      init()
      bool && $countDom && setTimeout(getCount,0)
    } else {
      getScript('https://cdn.jsdelivr.net/npm/twikoo@1.3.0/dist/twikoo.all.min.js').then(()=> {
        init()
        bool && $countDom && setTimeout(getCount,0)
      })
    }
  }

  if ('Twikoo' === 'Twikoo' || !true) {
    if (true) btf.loadComment(document.getElementById('twikoo-wrap'), loadTwikoo)
    else loadTwikoo(true)
  } else {
    window.loadOtherComment = () => {
      loadTwikoo()
    }
  }
})()</script></div><script defer src="//lib.baomitu.com/jquery/3.5.1/jquery.min.js"></script><script defer src="https://myhkw.cn/api/player/160561664166" id="myhk" key="160561664166" m="1"></script><div><canvas id="snow" style="position:fixed;top:0;left:0;width:100%;height:100%;z-index:99999;pointer-events:none"></canvas></div><script>const notMobile = (!(navigator.userAgent.match(/(phone|pad|pod|iPhone|iPod|ios|iPad|Android|Mobile|BlackBerry|IEMobile|MQQBrowser|JUC|Fennec|wOSBrowser|BrowserNG|WebOS|Symbian|Windows Phone)/i)));</script><scrip async type="text/javascript" src="https://cdn.jsdelivr.net/gh/Candinya/Kratos-Rebirth@latest/source/js/snow.min.js"></scrip><scrip defer src="https://cdn.jsdelivr.net/npm/hexo-theme-volantis@latest/source/js/issues.min.js"></scrip><script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script><script>var gitcalendar = new Vue({
  el: '#gitcalendar',
  data: {
    simplemode: true, 
    user: 'xiaoliblog',
    fixed: 'fixed',
    px: 'px',
    x: '',
    y: '',
    span1: '',
    span2: '',
    month: ['一月', '二月', '三月', '四月', '五月', '六月', '七月', '八月', '九月', '十月', '十一月', '十二月'],
    monthchange: [],
    oneyearbeforeday: '',
    thisday: '',
    amonthago: '',
    aweekago: '',
    weekdatacore: 0,
    datacore: 0,
    total: 0,
    datadate: '',
    data: [],
    positionplusdata: [],
    firstweek: [],
    lastweek: [],
    beforeweek: [],
    thisweekdatacore: 0,
    mounthbeforeday: 0,
    mounthfirstindex: 0,
    crispedges: 'crispedges',
    thisdayindex: 0,
    amonthagoindex: 0,
    amonthagoweek: [],
    firstdate: [],
    first2date: [],
    montharrbefore: [],
    monthindex: 0,
    color: ['#ebedf0', '#f1f8ff', '#dbedff', '#c8e1ff', '#79b8ff', '#2188ff', '#0366d6', '#005cc5', '#044289', '#032f62', '#05264c']
  },
  methods: {
    selectStyle(data, event) {
      document.querySelector('.angle-wrapper').style.display = 'block'
      this.span1 = data.date;
      this.span2 = data.count;
      this.x = event.clientX - 100;
      this.y = event.clientY - 60
    },
    outStyle() {
      document.querySelector('.angle-wrapper').style.display = 'none'
    },
    thiscolor(x) {
      if (x === 0) {
        let i = parseInt(x / 2);
        return this.color[0]
      } else if (x < 2) {
        return this.color[1]
      } else if (x < 20) {
        let i = parseInt(x / 2);
        return this.color[i]
      } else {
        return this.color[9]
      }
    },
  }
});
var apiurl = 'python-github-calendar-api-ruby.vercel.app' ? 'https://python-github-calendar-api-ruby.vercel.app/api?' : 'https://githubapi.ryanchristian.dev/user/'
var githubapiurl = apiurl + gitcalendar.user;
//canvas绘图
function responsiveChart() {
  let c = document.getElementById("gitcanvas");
  if (c) {
    let cmessage = document.getElementById("gitmessage");
    let ctx = c.getContext("2d");
    c.width = document.getElementById("gitcalendarcanvasbox").offsetWidth;
    let linemaxwitdh = 0.96 * c.width / gitcalendar.data.length;
    c.height = 9 * linemaxwitdh;
    let lineminwitdh = 0.8 * linemaxwitdh;
    let setposition = {
      x: 0.02 * c.width,
      y: 0.025 * c.width
    };
    for (let week in gitcalendar.data) {
      weekdata = gitcalendar.data[week];
      for (let day in weekdata) {
        let dataitem = {
          date: "",
          count: "",
          x: 0,
          y: 0
        };
        gitcalendar.positionplusdata.push(dataitem);
        ctx.fillStyle = gitcalendar.thiscolor(weekdata[day].count);
        setposition.y = Math.round(setposition.y * 100) / 100;
        dataitem.date = weekdata[day].date;
        dataitem.count = weekdata[day].count;
        dataitem.x = setposition.x;
        dataitem.y = setposition.y;
        ctx.fillRect(setposition.x, setposition.y, lineminwitdh, lineminwitdh);
        setposition.y = setposition.y + linemaxwitdh
      };
      setposition.y = 0.025 * c.width;
      setposition.x = setposition.x + linemaxwitdh
    };
    ctx.font = "600  Arial";
    ctx.fillStyle = '#aaa';
    ctx.fillText("日", 0, 1.9 * linemaxwitdh);
    ctx.fillText("二", 0, 3.9 * linemaxwitdh);
    ctx.fillText("四", 0, 5.9 * linemaxwitdh);
    ctx.fillText("六", 0, 7.9 * linemaxwitdh);
    let monthindexlist = c.width / 24;
    for (let index in gitcalendar.monthchange) {
      ctx.fillText(gitcalendar.monthchange[index], monthindexlist, 0.7 * linemaxwitdh);
      monthindexlist = monthindexlist + c.width / 12
    };
    cmessage.onmousemove = function(event) {
      document.querySelector('.angle-wrapper').style.display = 'none'
    };
    c.onmousemove = function(event) {
      document.querySelector('.angle-wrapper').style.display = 'none'
      getMousePos(c, event);
    };

    function getMousePos(canvas, event) {
      var rect = canvas.getBoundingClientRect();
      var x = event.clientX - rect.left * (canvas.width / rect.width);
      var y = event.clientY - rect.top * (canvas.height / rect.height);
      //console.log("x:"+x+",y:"+y);
      for (let item of gitcalendar.positionplusdata) {
        let lenthx = x - item.x;
        let lenthy = y - item.y;
        //console.log(lenthx,lenthy);
        if (0 < lenthx && lenthx < lineminwitdh) {
          if (0 < lenthy && lenthy < lineminwitdh) {
            //console.log(item.date,item.count)
            document.querySelector('.angle-wrapper').style.display = 'block'
            gitcalendar.span1 = item.date;
            gitcalendar.span2 = item.count;
            gitcalendar.x = event.clientX - 100;
            gitcalendar.y = event.clientY - 60
          }
        }
        //if(0< x - item.x <lineminwitdh&&0< y - item.y <lineminwitdh){
        //console.log(item.count,item.date);
        //}
      }
    }
  }
}
//数据统计算法
function addlastmonth() {
  if (gitcalendar.thisdayindex === 0) {
    thisweekcore(52);
    thisweekcore(51);
    thisweekcore(50);
    thisweekcore(49);
    thisweekcore(48);
    gitcalendar.thisweekdatacore += gitcalendar.firstdate[6].count;
    gitcalendar.amonthago = gitcalendar.firstdate[6].date
  } else {
    thisweekcore(52);
    thisweekcore(51);
    thisweekcore(50);
    thisweekcore(49);
    thisweek2core();
    gitcalendar.amonthago = gitcalendar.first2date[gitcalendar.thisdayindex - 1].date
  }
};

function thisweek2core() {
  for (let i = gitcalendar.thisdayindex - 1; i < gitcalendar.first2date.length; i++) {
    gitcalendar.thisweekdatacore += gitcalendar.first2date[i].count
  }
};

function thisweekcore(index) {
  for (let item of gitcalendar.data[index]) {
    gitcalendar.thisweekdatacore += item.count
  }
};

function addlastweek() {
  for (let item of gitcalendar.lastweek) {
    gitcalendar.weekdatacore += item.count
  }
};

function addbeforeweek() {
  for (let i = gitcalendar.thisdayindex; i < gitcalendar.beforeweek.length; i++) {
    gitcalendar.weekdatacore += gitcalendar.beforeweek[i].count
  }
};

function addweek(data) {
  if (gitcalendar.thisdayindex === 6) {
    gitcalendar.aweekago = gitcalendar.lastweek[0].date;
    addlastweek()
  } else {
    lastweek = data.contributions[51];
    gitcalendar.aweekago = lastweek[gitcalendar.thisdayindex + 1].date;
    addlastweek();
    addbeforeweek()
  }
}

fetch(githubapiurl)
  .then(data => data.json())
  .then(data => {
    gitcalendar.data = data.contributions;
    gitcalendar.total = data.total;
    gitcalendar.first2date = gitcalendar.data[48];
    gitcalendar.firstdate = gitcalendar.data[47];
    gitcalendar.firstweek = data.contributions[0];
    gitcalendar.lastweek = data.contributions[52];
    gitcalendar.beforeweek = data.contributions[51];
    gitcalendar.thisdayindex = gitcalendar.lastweek.length - 1;
    gitcalendar.thisday = gitcalendar.lastweek[gitcalendar.thisdayindex].date;
    gitcalendar.oneyearbeforeday = gitcalendar.firstweek[0].date;
    gitcalendar.monthindex = gitcalendar.thisday.substring(5, 7) * 1;
    gitcalendar.montharrbefore = gitcalendar.month.splice(gitcalendar.monthindex, 12 - gitcalendar.monthindex);
    gitcalendar.monthchange = gitcalendar.montharrbefore.concat(gitcalendar.month);
    addweek(data);
    addlastmonth();
    responsiveChart();
  })
  .catch(function(error) {
    console.log(error);
  });

//手机版更换为svg绘制
if (document.getElementById("gitcalendarcanvasbox").offsetWidth < 500) {
  gitcalendar.simplemode = false
}

//当改变窗口大小时重新绘制canvas
window.onresize = function() {
  if (gitcalendar.simplemode) responsiveChart()
}

//解决滚动滑轮时出现的标签显示
window.onscroll = function() {
  if (document.querySelector('.angle-wrapper')) {
    document.querySelector('.angle-wrapper').style.display = 'none'
  }
};</script></div><script src="/live2dw/lib/L2Dwidget.min.js?094cbace49a39548bed64abff5988b05"></script><script>L2Dwidget.init({"pluginRootPath":"live2dw/","pluginJsPath":"lib/","pluginModelPath":"assets/","tagMode":false,"log":false,"model":{"jsonPath":"/live2dw/assets/hijiki.model.json"},"display":{"position":"right","width":150,"height":300},"mobile":{"show":true},"react":{"opacity":0.7}});</script></body></html>